package BackTracking;

import java.util.LinkedList;
import java.util.List;

public class p17电话号码的字母组合 {
    class Solution {
        String[] map =
                {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        LinkedList<String> ans = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        public List<String> letterCombinations(String digits) {
            if(digits.length() == 0) return ans;
            backtracking(digits, 0);
            return ans;
        }

        // num用来判断递归层数
        public void backtracking(String digits, int num){
            // 判断结束递归
            if(num == digits.length()){
                ans.add(sb.toString());
                return;
            }
            int index = digits.charAt(num) - '0';
            String letters = map[index];
            for(int i = 0; i < letters.length(); i++){
                sb.append(letters.charAt(i));
                backtracking(digits, num + 1);
                sb.deleteCharAt(sb.length() - 1);
            }

        }
    }
}
